package gold.gold01;

import java.util.HashMap;
import java.util.Map;

/**
 * 中等
 * 快慢指针见 S0142环形链表II
 * 总之和Node有关的重复问题, 用map多少能搞出来
 * 回路用快慢指针, 循环用元素*2代替首尾拼接
 */
public class S0208环路检测 {

    /**
     * 7, 题解里的快慢指针有点好, 就一个走得快一个走得慢, 他俩迟早会相遇, 相遇的时候统计一下两者的步数就能得到环初始节点的位置
     * 有好几题链表找位置的题目都是用的map来做, 个人认为并没有耗什么内存, 因为存的只是个引用对象
     */
    public ListNode detectCycle(ListNode head) {
        if(head == null) return null;
        int count = 0;
        Map<ListNode, Integer> map = new HashMap<>();
        while(head != null){
            if(map.containsKey(head))
                return head;
            map.put(head, count++);
            head = head.next;
        }
        return null;
    }
}
